package b4_searchtree;

import java.util.NoSuchElementException;

/**
 * 普通的二分搜索树
 */
public class BST {
    private class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int val) {
            this.val = val;
        }
    }
    private int size;
    private TreeNode root;

    /** 添加元素 **/
    public void add(int val) {
        root = add(root, val);
    }
    //向以root为根节点的树添加元素
    private TreeNode add(TreeNode root, int val){
        //边界条件
        if(root == null){
            size ++;
            return new TreeNode(val);
        }
        if(val < root.val){
            //在左树中插入val
            root.left = add(root.left, val);
        }else if(val > root.val){
            //在右树中插入val
            root.right = add(root.right, val);
        }
        return root;
    }

    /** 查找元素 **/
    public boolean contains(int val) {
        return contains(root, val);
    }
    //判断根节点为root的二叉树中有无val
    private boolean contains(TreeNode root, int val) {
        //边界条件
        if(root == null){
            return false;
        }
        if(root.val == val){
            return true;
        }else if(root.val > val){
            return contains(root.left, val);
        }else{
            return contains(root.right, val);
        }
    }

    /** 返回最小值: 递归 **/
    public int findMin() {
        //判空
        if(size == 0){
            throw new NoSuchElementException("BST is empty! Cannot find!");
        }
        return findMin(root);
    }
    //返回以root为根节点的二叉树的最小值
    private int findMin(TreeNode root) {
        if(root.left == null){
            return root.val;
        }
        return findMin(root.left);
    }

    /** 返回最大值: 迭代 **/
    public int findMax() {
        //判空
        if(size == 0){
            throw new NoSuchElementException("BST is empty! Cannot find!");
        }
        TreeNode node = root;
        while (node.right != null){
            node = node.right;
        }
        return node.val;
    }

    /** 删除最小值: 递归 **/
    public int removeMin() {
        //判空
        if(size == 0){
            throw new NoSuchElementException("BST is empty! Cannot remove!");
        }
        int min = findMin();
        root = removeMin(root);
        return min;
    }
    //删除以root为根节点的二叉树的最小值
    private TreeNode removeMin(TreeNode root) {
        //当左子树不存在时
        if(root.left == null){
            //当前的root就是待删节点，则先暂存右子树的地址
            TreeNode right = root.right;
            //断开连接，并置为空
            root.right = root = null;
            size --;
            return right;
        }
        //左子树存在时，则递归去删左子树的最小值
        root.left = removeMin(root.left);
        return root;
    }

    /** 删除最大值: 递归 **/
    public int removeMax() {
        //日常判空
        if(size == 0){
            throw new NoSuchElementException("BST is empty! Cannot remove!");
        }
        int max = findMax();
        root = removeMax(root);
        return max;
    }
    //删除以root为根节点的二叉树的最大值
    private TreeNode removeMax(TreeNode root) {
        //当不存在右子树时
        if(root.right == null){
            //root就是最大值，待删节点
            TreeNode left = root.left;
            root.left = root = null;
            size --;
            return left;
        }
        //存在右子树时
        root.right = removeMax(root.right);
        return root;
    }

    /**
     * 删除任意值
     * Hibbard Deletion
     * 删除一个左右子树都存在的节点，就找到当前节点的前驱或后继来代替它。
     * 前驱、后继指的是大小关系上的，而不是left\right的指向
     * @return
     */
    public void remove(int val) {
        root = remove(root, val);
    }
    private TreeNode remove(TreeNode root, int val) {
        if(root == null){
            throw new NoSuchElementException("BST中没有值为" + val + "的节点");
        }else if(root.val < val){
            root.right = remove(root.right, val);
            return root;
        }else if(root.val > val){
            root.left = remove(root.left, val);
            return root;
        }else { //此时root就是待删节点
            if(root.left == null){
                return removeMin(root);
            }
            if(root.right == null){
                return removeMax(root);
            }
            //此时，左右子树都不为空
            //先找到右子树中的最小值节点
            TreeNode rightMin = minNode(root.right);
            //
            rightMin.right = removeMin(root.right);
            rightMin.left = root.left;
            root.left = root = null;
            root.right = root = null;
            return rightMin;
        }
    }
    //查找以root为根节点的树中最小值的节点
    private TreeNode minNode(TreeNode root) {
        if(root == null){
            throw new NoSuchElementException("BST is empty! Not have minNode!");
        }
        TreeNode node = root;
        while(node.left != null){
            node = node.left;
        }
        return node;
    }

    /** 打印二叉树 **/
    @Override
    public String toString() {
        return createBST(root, 1);
    }
    /**
     * 构造该节点的二叉树的图形,方式为前序遍历
     * 形参height为该节点处于二叉树的层数
     */
    private String createBST(TreeNode root, int height) {
        StringBuilder sb = new StringBuilder();
        //边界条件
        if(root == null){
            sb.append(branch(height)).append("NULL\n");
            return sb.toString();
        }
        //该节点不为空时，先构造该节点的图形
        sb.append(branch(height)).append(root.val).append("\n");
        //递归构造左子树的图形
        sb.append(createBST(root.left, height+1));
        //递归构造右子树的图形
        sb.append(createBST(root.right, height+1));
        return sb.toString();
    }
    //构造该层节点的树枝
    private String branch(int height) {
        if(height == 1){
            return "";
        }
        StringBuilder sb = new StringBuilder();
        while(height > 1){
            sb.append("--");
            height --;
        }
        return sb.toString();
    }
}
